package 堆.优先级队列;

/**
 * @description:
 * @author: ChenYunChou
 * @time: 2021/6/19 2021
 */
public class Heap {

    private int[] a = null;

    /**
     * 推的容量
     */
    private int n = 0;

    /**
     * 下沉
     * @param i
     */
    public void sink(int i){
        int j = 0;
        int t = a[i];
        ///找到i结点堆左子结点
        while ((j = (i << 1) + 1) < n){
            // j < n-1 判断是否有右子结点
            // 如果有，并且右子结点更大 那么j指向右子结点
            if (j < n-1 && a[j] < a[j+1]){
                j++;
            }
            //如果子结点比t大
            //那么t的位置还需要往后排
            if(a[j] > t){
                a[i] = a[j];
                i = j;
            }else {
                //找到了t的位置
                //此时t是大于所有的子结点的
                break;
            }
        }
        a[i] = t;
    }

    public void swim(int i){
        int t = a[i];
        int par = 0;
        //如果还存在父结点
        while (i > 0 && (par = (i -1) >> 1) != i){
            //如果父结点比t值小
            if (a[par] < t){
                a[i] = a[par];
                i = par;
            }else {
                break;
            }
        }
        a[i] = t;
    }

    public void push(int v){
        //push 是先把元素追加到数组尾巴上，然后在执行上浮操作
        a[n++] = v;
        swim(n-1);
    }

    public int pop(){
         int ret = a[0];
         a[0] = a[--n];
         sink(0);
         return ret;
    }

    public int size(){
        return n;
    }

    public static void main(String[] args) {
        int i = 0;
        int a = i;
        i++;
        System.out.println(a);
    }

}
